package com.leetcode.根据算法进行分类.动态规划算法相关;

import java.util.ArrayList;
import java.util.List;

/**
 * @author: xiaomi
 * @date: 2021/1/9
 * @description: 121. 买卖股票的最佳时机
 * https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/
 */
public class A_121_买卖股票的最佳时机 {

    public static void main(String[] args) {
        final A_121_买卖股票的最佳时机 action = new A_121_买卖股票的最佳时机();
        int[] prices = new int[]{7, 1, 5, 3, 6, 4};
        prices = new int[]{2, 4, 1, 11, 7};
        final int res = action.maxProfit(prices);
        System.out.println("res = " + res);
    }

    /**
     * 虽然做出来了，但是才打败 5%！
     * 看看动态规划有多厉害！！！
     * --
     * 即使我增加了一些规律，但还是接近于暴力解法！
     *
     * @param prices
     * @return
     */
    public int maxProfit(int[] prices) {
        int res = 0;
        if (prices == null || prices.length < 2) {
            return res;
        }
        //可能的买入点
        List<Integer> inList = new ArrayList<>();
        //可能的卖出点
        List<Integer> outList = new ArrayList<>();
        //增加首尾元素的判断
        if (prices[1] >= prices[0]) {
            inList.add(0);
        }
        if (prices[prices.length - 1] >= prices[prices.length - 2]) {
            outList.add(prices.length - 1);
        }
        int preValue = prices[0];
        for (int i = 0; i < prices.length; i++) {
            if (prices[i] < preValue) {
                if (!inList.isEmpty()) {
                    outList.add(i - 1);
                }
                inList.add(i);
            }


            preValue = prices[i];
        }
        int max = 0;
        //根据 inList 进行推演
        for (int i = 0; i < inList.size(); i++) {
            for (int j = 0; j < outList.size(); j++) {
                if (outList.get(j) < inList.get(i)) {
                    continue;
                }
                int value = prices[outList.get(j)] - prices[inList.get(i)];
                max = Math.max(value, max);
            }
        }
        return max;
    }

    /**
     * 通过动态规划求解
     * 初见动态规划，感觉就是在执行的过程中，可以修改变量，影响最终的结果
     * --
     * woc
     * 提高了两个数量级!
     * 分析:
     * 在一次遍历中确认最低值 minPrice，并且保留 最大的差价 maxProfit
     * @param prices
     * @return
     */
    public int maxProfitByDynamicPlanning(int[] prices) {
        int maxProfit = 0;
        if (prices == null || prices.length < 2) {
            return maxProfit;
        }
        int minPrice = prices[0];
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] <= minPrice) {
                minPrice = prices[i];

            } else {
                maxProfit = Math.max(maxProfit, prices[i] - minPrice);
            }
        }
        return maxProfit;
    }
}
